package com.lry.basic.algorithm.bit;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/19
 */
//给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
//        示例 1:
//        输入: 2
//        输出: [0,1,1]
//
//        示例 2:
//        输入: 5
//        输出: [0,1,1,2,1,2]
public class CountBits {
    public static void main(String[] args) {
        int[] is =  countBits(5);
        for (int i:is) {
            System.out.println(i);
        }
    }
    public static int[] countBits(int num) {
        int []  res = new int[num+1];
        for(int i =num;i>=0;i--){
            res[i] = count(i);
        }
        return res;
    }

    public int[] countBits2(int num) {
        int[] ans = new int[num + 1];
        for (int i = 1; i <= num; ++i)
            ans[i] = ans[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
        return ans;
    }

    public static int count(int num){
        int count = 0;
        while(num>0){
            count++;
            num = num&(num-1);
        }
        return count;
    }

}
